import java.util.*;

public class Test {
    /*
    复习
     */
    /*
    题目 1：移动 0
     */
    // 双指针：
    // cur 和 dest 将 nums 区间分成三个部分：
    // 首先 cur 将区间分成 已处理的 和 未处理的
    // dest 又将 已处理区间分为 非0 和 0
    // [0, dest] , [dest + 1, cur - 1], [cur, n - 1]
    public void moveZeroes(int[] nums) {
        int cur = 0;
        int dest = - 1;
        int n = nums.length;

        while(cur < n){
            if(nums[cur] != 0){
                dest++;
                swap(nums, dest, cur);
            }
            cur++;

        }
    }

    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /*
    题目 2：复写 0
     */
    public void duplicateZeros(int[] arr) {
        int cur = 0;
        int dest = -1;

        int n = arr.length;

        // 1. 找到最后一个需要被复写的 0
        while(cur < n){
            if(arr[cur] != 0) dest += 1;
            else dest += 2;
            if(dest >= n - 1){
                break;
            }
            cur++;
        }

        // 2. 处理边界情况
        if(dest == n){
            arr[n - 1] = 0;
            cur--;
            dest -= 2;
        }

        // 3. 复写
        while(cur >= 0){
            if(arr[cur] != 0){
                arr[dest] = arr[cur];
                dest--;
                cur--;
            }else{
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }

    /*
    题目 3: 快乐数
     */
    // 使用 鸽巢原理 可以知道 一个数经过有限次的取平方和最后一定会循环，不管循环的结果是不是 1.
    public int bitSum(int n){
        int sum = 0;

        while(n > 0){
            int t = n % 10;
            sum += t * t;
            n /= 10;
        }

        return sum;
    }
    public boolean isHappy(int n) {
        int slow = n;
        int fast = bitSum(n);

        while(fast != slow){
            slow = bitSum(slow);
            fast = bitSum(bitSum(fast));
        }

        return slow == 1;
    }

    /*
    题目 4：盛最多水的容器！
     */
    // 初始想法：暴力枚举 ——> 超时！！
    // 是否能减少枚举次数呢？
    // 答案是可以的
    // V = H * W
    // 1. H 减少，W 减少，则 V 减少 !
    // 2. H 不变，W 减少，则 V 减少 !
    public int maxArea(int[] h) {
        int left = 0;
        int right = h.length - 1;

        int ret = 0; //因为没有小于 0 的数字，所以 ret 取 0 即可

        while(left < right){
            int v = Math.min(h[left], h[right]) * (right - left);
            ret = Math.max(ret, v);
            if(h[left] < h[right]){
                left++;
            }else{
                right--;
            }
        }

        return ret;
    }

    /*
    题目 5 : 环形子数组的最大和
     */
    // 环形子数组的最大和 解题思路可以和 连续子数组最大和类似
    // 连续子数组最大和 + 连续子数组最小和
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;

        // 为了不在循环的外头初始化，才多申请一个空间的！
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];

        int max = nums[0];
        int min = nums[0];
        int sum = 0;

        for(int i = 1; i < n + 1; i++){
            int x = nums[i - 1];
            f[i] = Math.max(x, x + f[i - 1]);
            max = Math.max(f[i], max);

            g[i] = Math.min(x, x + g[i - 1]);
            min = Math.min(g[i], min);

            sum += x;
        }

        return sum == min ? max : Math.max(max, sum - min);
    }

    /*
    题目 6：最大子数组和
     */
    public int maxSubArray(int[] nums) {
        int n = nums.length;

        int[] f = new int[n + 1];
        int max = nums[0];

        for(int i = 1; i < n + 1; i++){
            f[i] = Math.max(nums[i - 1], nums[i - 1] + f[i - 1]);
            max = Math.max(f[i], max);
        }

        return max;
    }

    /*
    题目 7：最佳买卖股票时机含冷冻期!
     */
    public int maxProfit(int[] p) {
        int n = p.length;

        int[][] dp = new int[n][3];

        dp[0][0] = -p[0];
        dp[0][1] = 0;
        dp[0][2] = 0;

        for(int i = 1; i < n; i++){
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - p[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][0] + p[i];
        }

        return Math.max(dp[n - 1][1], dp[n - 1][2]);
    }

    /*
    题目 8：最佳买卖股票时机含手续费!
     */
    public int maxProfit1(int[] p, int fee) {
        int n = p.length;

        int[][] dp = new int[n][2];

        dp[0][0] = -p[0];
        dp[0][1] = 0;

        for(int i = 1; i < n; i++){
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - p[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - fee + p[i]);
        }

        return dp[n - 1][1];
    }

    // 两种状态的，使用两个一维的数组比使用一个二维数组来得快些！
    public int maxProfit2(int[] p, int fee) {
        int n = p.length;

        int[] f = new int[n];
        int[] g = new int[n];

        f[0] = -p[0];

        for(int i = 1; i < n; i++){
            f[i] = Math.max(f[i - 1], g[i - 1] - p[i]);
            g[i] = Math.max(g[i - 1], f[i - 1] - fee + p[i]);
        }

        return g[n - 1];
    }

    /*
    题目 9：买卖股票的最佳时机Ⅲ
     */
    // 不大会写！
    public int maxProfit3(int[] p) {
        int n = p.length;

        int[][] f = new int[n][3];
        int[][] g = new int[n][3];

        int INF = -0x3f3f3f3f;

        for(int i = 0 ; i < 3 ; i++){
            f[0][i] = g[0][i] = INF;
        }

        f[0][0] = -p[0];
        g[0][0] = 0;

        for(int i = 1; i < n; i++){
            for(int j = 0; j < 3; j++){
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - p[i]);
                g[i][j] = g[i - 1][j];
                if(j - 1 >= 0){
                    g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + p[i]);
                }
            }
        }

        int ret = Integer.MIN_VALUE;

        for(int i = 0; i < 3; i++){
            ret = Math.max(ret, g[n - 1][i]);
        }

        return ret;
    }

    /*
    题目 10 ：买卖股票的最佳时机Ⅳ：
     */
    public int maxProfit(int k, int[] p) {
        int n = p.length;

        int[][] f = new int[n][k + 1];
        int[][] g = new int[n][k + 1];

        int INF = -0x3f3f3f3f;

        for(int i = 0; i < k + 1; i++){
            f[0][i] = g[0][i] = INF;

        }

        f[0][0] = -p[0];
        g[0][0] = 0;

        for(int i = 1; i < n; i++){
            for(int j = 0; j < k + 1; j++){
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j]- p[i]);
                g[i][j] = g[i - 1][j];
                if(j - 1 >= 0){
                    g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + p[i]);
                }
            }
        }

        int ret = Integer.MIN_VALUE;

        for(int i = 0; i < k + 1; i++){
            ret = Math.max(ret, g[n - 1][i]);
        }

        return ret;
    }

    /*
    题目 11 : 有效三角形的个数
   */
    // 先解决：有 n 个数，以 3 个为一组，能形成多少组？重复的也行
    // 暴力枚举，O(3N³)
    // 利用排序来进行优化！
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);

        int left = 0;
        int fix = nums.length - 1;
        int right = fix - 1;
        int count = 0;

        while(fix >= 2){
            while(left < right ){
                if(nums[left] + nums[right] > nums[fix]){
                    count += (right - left);
                    right--;
                }else{
                    left++;
                }
            }
            fix--;
            right = fix - 1;
            left = 0;
        }

        return count;
    }

    // 时间复杂度为 O(n²)
    public int triangleNumber1(int[] nums) {
        Arrays.sort(nums);

        int count = 0;
        int n = nums.length;

        for(int i = n - 1; i >= 2; i--){
            int left = 0;
            int right = i - 1;
            while(left < right){
                if(nums[left] + nums[right] > nums[i]){
                    count += right - left;
                    right--;
                }else{
                    left++;
                }
            }
        }
        return count;
    }

    /*
    题目 12：和为 s 的两个数
     */
    // 方法一：哈希表
    public int[] twoSum(int[] nums, int target) {
        Set<Integer> set = new HashSet<>();
        int[] arr = new int[2];
        int i = 0;

        for(int x : nums){
            if(set.contains(target - x)){
                arr[0] = x;
                arr[1] = target - x;
                return arr;
            }else{
                set.add(x);
            }
        }

        return arr;
    }

    // 但这个题目有一个条件没有被用到！
    // 那就是这是个递增的排序数组！
    // 利用数组的单调递增性质，使用双指针！！
    public int[] twoSum1(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int[] arr = new int[2];

        while(left < right){
            int sum = nums[left] + nums[right];
            if(sum > target){
                right--;
            }else if(sum < target){
                left++;
            }else{
                arr[0] = nums[left];
                arr[1] = nums[right];
                return arr;
            }
        }

        return arr;
    }
}
